package com.sort;

import com.sun.corba.se.impl.logging.InterceptorsSystemException;

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;

public class test {
    public static void main(String[] args) {
        int arr[] = {5,8, 9, 1, 7, 2, 3, 5, 4, 6, 0,8,2};

       quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }


    public static void insertSort(int[] arr){
        //待插入的数
        int value = 0;
        //插入的位置
        int index = 0;
        for(int i = 1 ; i < arr.length;i++){
            value = arr[i];
            index = i-1;
            //将待插入的数从后往前和以排序好的数进行比较
            while(index >=0 && arr[index] > value){
                arr[index+1] = arr[index];
                index--;
            }
            //循环结束也就是直到遇到比自己小的数，插入到数的后面
            if(index+1 != i){
                arr[index + 1] = value;
            }
        }
    }

    public static void shellSort(int[] arr){
        int value = 0;
        int index = 0;
        for(int gap = arr.length/2; gap > 0;gap /= 2){
            for(int i = gap;i<arr.length;i++){
                value = arr[i];
                index = i - gap;
                while(index >= 0 && arr[index] > value){
                    arr[index+gap] = arr[index];
                    index-=gap;
                }
                if(index+gap != i){
                    arr[index+gap] = value;
                }
            }
        }
    }

    public static void quickSort(int[] arr,int left,int right){
        if(left > right){
            return;
        }
        int l = left;
        int r = right;
        int pivot = arr[left];
        int temp;
        while(l < r){
            while(arr[r] >= pivot && l < r){
                r--;
            }
            while (arr[l] <= pivot && l < r){
                l++;
            }
            if(l<r){
                temp = arr[r];
                arr[r] = arr[l];
                arr[l] = temp;
            }
        }
        arr[left] = arr[l];
        arr[l] = pivot;
        quickSort(arr,left,l-1);
        quickSort(arr,r+1,right);
    }

    public static void radixSort(int arr[]) {
        HashMap<Integer, LinkedList<Integer>> bucket = new HashMap<>();
        //对Map进行初始化
        for(int i = 0;i<10;i++){
            bucket.put(i,new LinkedList<Integer>());
        }
        //基数排序排序的次数即为最大值的位数，所以首先要获取数组中的最大值以及位数
        int maxVal = arr[0];
        for(int i = 1;i < arr.length;i++){
            if(arr[i] > maxVal){
                maxVal = arr[i];
            }
        }
        int maxLength = (maxVal+"").length();
        for(int i = 0,n=1;i<maxLength;i++,n *= 10){
            //将每个数放入到对应的桶中
            for(int  j = 0;j<arr.length;j++){
                int index = (arr[j]/n) % 10;
                bucket.get(index).add(arr[j]);
            }
            int index = 0;
            //将桶中的元素放回原来的数组中
            for(int j = 0;j <10;j++){
                for(Integer num : bucket.get(index)){
                    arr[index++] = num;
                }
            }
            for(int j=0;j<10;j++){
                bucket.get(j).clear();                                  
            }
        }
    }
}
